"""
3. 假设你正在爬楼梯。需要n阶才能到达楼顶
   每次你可以爬1或者2个台阶。你有多少种不同的方法可以爬到楼顶呢？

   注意: 给定的 n 是一个整数。



题目解析:
找规律：
    f(1) 一个台阶有 1 种可能
    f(2) 两个台阶有 2 种可能
        第一步上 1 个台阶 
        第一步上 2 个台阶
    f(3) 三个台阶有 2 + 1 = 3 种可能
        第一步上 1 个台阶
            1 2
            1 1 1 
            2 种
        第一步上 2 个台阶
            2 1
            1 种
    f(4) 四个台阶有 3 + 2 = 5 种可能
        第一步上 1 个台阶 3
            1 1 1 1
            1 2 1
            1 1 2
        第一步上 2 个台阶 2
            2 2
            2 1 1
    f(5) 5 个台阶有 3 + 5 =8 种可能
        第一步上 1 个台阶
            1 1 1 1 1
            1 1 1 2
            1 1 2 1
            1 2 1 1
            1 2 2
        第一步上 2 个台阶
            2 1 1 1
            2 1 2
            2 2 1
    得 f(n) = f(n-1) + f(n-2)   
"""

# 解法一： 递归解法

def getCount1(n: int) -> int:
    if n == 1:
        return 1
    if n == 2:
        return 2
    
    return getCount1(n-1) + getCount1(n-2)


# 解法二: 动态规划思维，自底向上， 将结果存起来，避免重复计算
"""
    这里使用了一个 斐波那契额的 技巧， 当然也可以把所有结果放到列表中存起来
"""

def getCount2(n: int) -> int:
    a = 1
    b = 2
    if n == 1 or n == 2:
        return n
    
    for i in range(3, n+1):
        b, a = a+b, b
    
    return b


result1 = getCount1(5)
print("递归解法", result1)

result1 = getCount2(7)
print("动态规划解法", result1)
